/*
 * Project: Sudoku Explainer
 * Copyright (C) 2006-2007 Nicolas Juillerat
 * 
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.rules.naked;

import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

import com.onegravity.sudoku.solver.HintResource;
import com.onegravity.sudoku.solver.R;
import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.IndirectHint;
import com.onegravity.sudoku.solver.core.IndirectHintProducer;
import com.onegravity.sudoku.solver.data.Block;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Column;
import com.onegravity.sudoku.solver.data.ExtraRegionExtended;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.data.Region;
import com.onegravity.sudoku.solver.data.Row;
import com.onegravity.sudoku.solver.util.CommonTuples;
import com.onegravity.sudoku.solver.util.Permutations;

/**
 * Implementation of the naked sets solving techniques
 * (Naked Pair, Naked Triplet, Naked Quad).
 */
public class NakedSubsetProducer implements IndirectHintProducer {

	private int degree;

    public NakedSubsetProducer(int degree) {
        this.degree = degree;
    }

    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
        if (grid.hasExtraRegions()) {
        	getHints(grid, ExtraRegionExtended.class, accu);
        }
        getHints(grid, Block.class, accu);
        getHints(grid, Column.class, accu);
        getHints(grid, Row.class, accu);
    }

    /**
     * For each regions of the given type, check if a n-tuple of values have
     * a common n-tuple of potential positions, and no other potential position.
     * @throws InterruptedException 
     */
    private <T extends Region> void getHints(Grid grid, Class<T> regionType, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
        Region[] regions = grid.getRegions(regionType);
        // Iterate on parts
        Permutations perm = new Permutations(degree, 9);
        Cell[] cells = new Cell[degree];
        BitSet[] potentialValues = new BitSet[degree];
        for (Region region : regions) {
            if (region.getEmptyCellCount() >= degree * 2) {
                perm.reset();
                // Iterate on tuples of positions
                while (perm.hasNext()) {
                    if (Thread.interrupted()) throw new InterruptedException();
                    int[] indexes = perm.nextBitNums();

                    // Build the cell tuple
                    for (int i = 0; i < cells.length; i++) {
                        cells[i] = region.getCell(indexes[i]);
                    }

                    // Build potential values for each position of the tuple
                    for (int i = 0; i < degree; i++) {
                        potentialValues[i] = cells[i].getPotentialValues();
                    }

                    // Look for a common tuple of potential values, with same degree
                    BitSet commonPotentialValues = CommonTuples.searchCommonTuple(potentialValues, degree);
                    if (commonPotentialValues != null) {
                        // Potential hint found
                        IndirectHint hint = createValueUniquenessHint(region, cells, commonPotentialValues);
                        if (hint!=null && hint.isWorth()) accu.add(hint);
                    }
                }
            }
        }
    }

    private IndirectHint createValueUniquenessHint(Region region, Cell[] cells, BitSet commonPotentialValues) {
        // Build removable potentials
        Map<Cell,BitSet> cellRemovePValues = new HashMap<Cell,BitSet>();
        for (int i = 0; i < 9; i++) {
            Cell otherCell = region.getCell(i);
            if (!Arrays.asList(cells).contains(otherCell)) {
                // Get removable potentials
                BitSet removablePotentials = null;
                for (int value = 1; value <= 9; value++) {
                    if (commonPotentialValues.get(value) && otherCell.hasPotentialValue(value)) {
                        if (removablePotentials==null) removablePotentials = new BitSet(10);
                        removablePotentials.set(value);
                    }
                }
                if (removablePotentials!=null && !removablePotentials.isEmpty()) {
                    cellRemovePValues.put(otherCell, removablePotentials);
                }
            }
        }
        if (cellRemovePValues.isEmpty()) return null;
        
        // Build value list
        int[] values = new int[degree];
        int dstIndex = 0;
        for (int value = 1; value <= 9; value++) {
            if (commonPotentialValues.get(value)) {
                values[dstIndex++] = value;
            }
        }
        
        // Build concerned cell potentials
        Map<Cell,BitSet> cellPValues = new LinkedHashMap<Cell,BitSet>();
        for (Cell cell : cells) {
            BitSet potentials = new BitSet(10);
            potentials.or(commonPotentialValues);
            potentials.and(cell.getPotentialValues());
            cellPValues.put(cell, potentials);
        }
        
        return new NakedSubsetHint(cells, values, cellPValues, cellRemovePValues, region);
    }

	@Override
	public String getProducerName() {
		int id = R.string.producer_naked_pair;
		switch(degree) {
		case 2: id =  R.string.producer_naked_pair; break;
		case 3: id =  R.string.producer_naked_triple; break;
		case 4: id =  R.string.producer_naked_quad; break;
		}
		return HintResource.getString(id);
	}
}